struct Solution;

impl Solution {
//     pub fn mct_from_leaf_values(arr: Vec<i32>) -> i32 {
//         let mut map = HashMap::new();
//         Solution::help(&arr, 0, arr.len(), &mut map);
//         let vec = map.get(&(0, arr.len())).unwrap();
//         let mut result = std::i32::MAX;
//         for (_, sum) in vec.iter() {
//             if *sum < result {
//                 result = *sum;
//             }
//         }
//         result
//     }
//
//     // 每一个范围都可以削减为一个更小的范围
//     // 例如 6 2 4 7
//     // 可以拆分为 6 和 2 4 7
//     // 2 4 7 可以拆分为 2 和 4 7 或 2 4 和 7
//     // 很显然 如果数组只有两个数字 无法进一步把问题拆分
//     // 只有一个数字时 也无法拆分
//     fn help(arr: &[i32], start: usize, end: usize, map: &mut HashMap<(usize, usize), Vec<(i32, i32)>>) {
//
//         // 防止重复计算
//         if map.get(&(start, end)).is_some() {
//             return;
//         }
//         // 只有一个值，无需拆分
//         if start + 1 == end {
//             let mut vec = vec![];
//             // 如果一个值，最大是自己
//             vec.push((arr[start], 0));
//             map.insert((start, end), vec);
//             return;
//         }
//         // 两个值也可以不拆分
//         if start + 2 == end {
//             let mut vec = vec![];
//             let max = i32::max(arr[start], arr[start + 1]);
//             vec.push((max, arr[start] * arr[start + 1]));
//             map.insert((start, end), vec);
//             return;
//         }
//         // 这个范围的容器
//         let mut vec = vec![];
//         // 一个一个数拆分出来
//         for mid in (start + 1)..end {
//             Solution::help(arr, start, mid, map);
//             Solution::help(arr, mid, end, map);
//
// //            let left_vec = map.get(&(start, mid)).unwrap();
// //            let right_vec = map.get(&(mid, end)).unwrap();
//
//             for (left_max, left_sum) in map.get(&(start, mid)).unwrap().iter() {
//                 for (right_max, right_sum) in map.get(&(mid, end)).unwrap().iter() {
//                     let max = i32::max(*left_max, *right_max);
//                     let root = *left_max * *right_max;
//                     let root_sum = *left_sum + *right_sum + root;
//                     vec.push((max, root_sum));
//                 }
//             }
//         }
//         map.insert((start, end), vec);
//     }

    /// DP解法
    pub fn mct_from_leaf_values(_arr: Vec<i32>) -> i32 {
        1
    }
}

fn main() {
    let vec = vec![14, 8, 7, 5, 4, 8, 5, 9, 9, 2, 11, 3, 5, 13, 3, 14, 8];
    let result = Solution::mct_from_leaf_values(vec);
    println!("{}", result);
}


// https://leetcode.com/problems/minimum-cost-tree-from-leaf-values/discuss/339959/One-Pass-O(N)-Time-and-Space
